package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 错误写法
 * warnning
 * minmax
 * //bug1: 右子树的写法是错误的, 不是简单的mid+x :childMinMax = Math.max(childMinMax, mid + state[i - mid]);
 * //bug2: 这是一个满二叉树的想法从根本上就是错误的
 * //bug3: 这是一个左右子树的sum平衡的树的想法也是错误的
 * <p>
 * see 887
 *
 * @author tzp
 * @since 2020/9/15
 */
public class LC375 implements DynamicProblem {
    public int getMoneyAmount(int n) {
        if (n <= 1) return 0;
        if (n == 2) return 1;

        int mi = 1;
        int[] state = new int[n + 1];
        state[0] = 0;
        state[1] = 0;
        state[2] = 1;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 0;
        nums[2] = 1;
        for (int i = 3; i <= n; i++) {
            while ((Math.pow(2, mi) - 1) < i) {//n个节点的满树的高度
                mi++;
            }
            //找中间节点
            int mid = (int) (i - (Math.pow(2, mi - 2) - 1));//i-上层半树
            int exceedHalf = (int) (Math.pow(2, mi - 2) + Math.pow(2, mi - 1) - 1);
            if (i > exceedHalf) {
                mid = mid - (i - exceedHalf);
            }
            int lchildMinMax = state[mid - 1];
            int rchildMinMax = mid * nums[i - mid] + state[i - mid];
            if (lchildMinMax > rchildMinMax) {
                state[i] = mid + lchildMinMax;
                nums[i] = 1 + nums[mid - 1];
            } else {
                state[i] = mid + rchildMinMax;
                nums[i] = 1 + nums[i - mid];
            }
        }
        return state[n];
    }

    public static void main(String[] args) {
//        System.out.println(Math.pow(2, 3));
//        System.out.println(new LC375().getMoneyAmount(6));
//        System.out.println(new LC375().getMoneyAmount(7));
        System.out.println(new LC375().getMoneyAmount(12));
    }
}
